package LeetCode;

public class Code221_maximalSquare {

    public int maximalSquare(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int res = 0;
        for (int j = 0; j < n; j++){
            dp[0][j] = matrix[0][j] == '0' ? 0 : 1;
            res = Math.max(res, dp[0][j]);
        }
        for (int i = 0; i < m; i++) {
            dp[i][0] = matrix[i][0] == '0' ? 0 : 1;
            res = Math.max(res, dp[i][0]);
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '0'){
                    dp[i][j] = 0;
                } else { // ==1
                    int temp = Math.min(dp[i-1][j], Math.min(dp[i][j-1],
                            dp[i-1][j-1]));
                    dp[i][j] = temp == 0 ? 1 : (int) Math.pow(Math.sqrt(temp) + 1, 2);
                }
                res = Math.max(res, dp[i][j]);
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Code221_maximalSquare code221_maximalSquare = new Code221_maximalSquare();
        char[][] ma = new char[][]{{'1','1','1','1','0'},
                                    {'1','1','1','1','0'},
                                    {'1','1','1','1','1'},
                                    {'1','1','1','1','1'},
                                    {'0','0','1','1','1'}};
        System.out.println(code221_maximalSquare.maximalSquare(ma));
    }
}
